# -*- coding: utf-8 -*-
# @Time    : 2022/3/23 16:23
# @Author  : Zhouyiqun 20191583
# @File    : lab1_rsa.py
# @Software: PyCharm

# 求最大公约数
def gcd(a, b):
    while a!=0:
        a,b= b%a, a
    return b

#扩展阿基米德求模逆
def findModReverse(a,m):
        if gcd(a,m)!=1:
            return None
        u1,u2,u3 = 1,0,a
        v1,v2,v3 = 0,1,m
        while v3!=0:
            q = u3//v3
            v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
        return u1%m

def do_encrypt(c):
    # generate ciphertext
    return pow(ord(c), e) % n

# -- set paras ---
q = 61 # fixed primes
p = 53
n = p * q # primes product
el = (p - 1) * (q - 1) # Euler
e = 17 # e
d = findModReverse(e, el) # solve d

# -- msg encode ---
msg= 'CQUINFORMATIONSECURITYEXP1'
msg_l= list(msg)
# -- encrypt ---
print("*** 输入明文 ***")
print(msg)
cpt=[]
for c in msg_l:
    cpt.append(do_encrypt(c))
print("公钥=","(", n,",",e,")")
# --- transport ciphertext ---
print("*** 发送密文 ***")
for c in cpt:
    print(chr(c), end="")
print()
# --- decrypt ---
dcpt=[]
for c in cpt:
    dc = pow(c, d) % n
    dcpt.append(chr(dc))
# --- decode ---
print("*** 解密 ***")
print("私钥=","(", n,",",d,")")
print(''.join(dcpt))